Diseño e implementación (página 2)

Partes: 1, 2

Subsistemas vista, control y aplicación
Vistas al exterior: multiples visualizaciones de datos y funciones, requiere mecanismos de verificación de la integridad de los objetos mostrados al usuario.
Controlador de entrada: gestiona las entradas, y puede tener un reloj y agenda asociados.
Aplicación: datos (conceptos y relaciones) +funciones (inferencias y tareas). Dos implementaciones: programación funcional, orientada a objetos.

Subsistema aplicación visto de forma orientada a objetos
(Gp:) Tarea
metaclases I/O
método

(Gp:) Método de tarea
metaclases interm
especif. control

(Gp:) Metaclase
metaclases I/O
método

(Gp:) Inferencia
metaclases I/O
vista-dominio

(Gp:) Concepto
metaclases I/O
método

Paso 2 Identificar plataforma HW- SW
Requisitos de usuario
Elección de SW más importante que HW, excepto en aplicaciones en tiempo real.
Disponibilidad de código pre-existente para su reutilización en el subsistema de vistas al exterior.
Disponibilidad de código pre-existente para su reutilización al representar el conocimiento del dominio.
Facilidad de integración con otro software.
Lenguaje fuertemente/debilmente 'tipado'
Existencia de mecanismos complejos de control de ejecución.
Herramientas CASE disponibles.

Ejemplo de evaluación plataforma SW
Java vs. Prolog.
Java más librerías para el interfaz que prolog.
Prolog más facilidad para representar conocimiento.
Tipado de java más fuerte que prolog.
Protocolos de control de ejecución más complejos en Java.

Paso 3 especificar componentes de la arquitectura
Vistas al exterior:
Especificar los componentes del interfaz.
Diseñar mecanismos de actualización y verificación de integridad de la información mostrada en la misma.
Interfaz de usuario/interfaz de experto.
Control de entradas:
Determinar condiciones de activación/terminación de funciones de la aplicación.
Gestión de funciones de transferencia.
Interrupciones del usuario permitidas.

Especificar componentes del subsistema de la aplicación
Tarea: métodos para inicializar y ejecutar la tarea.
Inferencia: métodos para ejecutar, new-solution, has-solution, relación de con conceptos del dominio.
Transferencia: mediante paso de mensajes a los otros dos subsistemas.
Metaclases: tipos de datos (elemento, conjunto o lista), operaciones de acceso: asignación, add, select, substract, etc.
Conceptos: métodos de acceso y modificación de atributos.

Paso 4 concretar diseño final
Dos subpasos:
Establecer correspondencia entre elementos del modelo conceptual y componentes de la arquitectura del sistema: controlador, vistas y aplicación
Añadir detalles concretos al diseño para hacer operativa a la arquitectura.

Correspondencia del controlador
Debe preservar lo establecido por el modelo de cooperación.
A menudo es necesario hacerlo 'ad-hoc' y con mucho trabajo manual.
Lo mínimo es la gestión de interrupciones.
Adicionalmente:
Dar respuesta a petición de explicaciones.
Permitir un cierto control del usuario sobre el proceso de razonamiento.
Posibilitar el enunciado de variantes de un escenario.

Correspondencia de las vistas al exterior
Seleccionar una o varias formas de mostrar la información.
Para el usuario final, es preciso mostrar la información con un formato lo más próximo posible al dominio.
Ajustar la representación de la información a la práctica cotidiana del dominio.

Correspondencia con la aplicación
Mínimo conjunto de actividades:
Para cada método de tarea, construir un algoritmo que ejecute fielmente la estructura de control.
Para cada concepto, escoger y construir el tipo estructurado de datos correspondiente.
Para cada inferencia, escribir un método que la invoque y modifique las estructuras de datos de forma adecuada.

Un ejemplo de diseño detallado
Implementación en prolog de frágmento de SBC de diagnóstico médico (ejemplo completo en Schreiber, 1992).
2 inferencias abstraer y especificar.
2 conceptos: datos-cuantitativos y datos-cualitativos, subtipos de datos paciente.
2 relaciones: definición, abstracción.

Conceptos
CONCEPT datos-paciente;
ATTRIBUTES:
nombre: STRING;
END CONCEPT.
CONCEPT datos-cuantitativos;
SUB-TYPE-OF datos-paciente;
ATTRIBUTES:
temperatura: NUMBER-RANGE(35-42);
presión: NUMBER-RANGE(0-300);
END CONCEPT.

Conceptos
CONCEPT datos-cualitativos;
SUB-TYPE-OF datos-paciente;
ATTRIBUTES:
fiebre: BOOLEAN;
presion-sangre:
VALUE-TYPE elevacion;
TYPE: NOMINAL;
VALUE-LIST: {normal, elevada};
END VALUE-TYPE.
hipertensión: elevacion;
END CONCEPT;

Conceptos – Prolog
concepto(nombre, super)
concepto(datos_paciente, []).
concepto(datos_cualitativos, [datos_paciente]).
concepto(datos_cuantitativos, [datos_paciente]).
atributos(concepto, nombre, valores)
atributos(datos_cuantitativos, temperatura, numberrange(35.0,42.0)).
atributos(datos_cualitativos, hipertension, [normal, elevada]).
…

Relaciones
RELATION abstraccion;
ARGUMENTS: datos-cuantitativos. Datos-cualitativos.
AXIOMS: fiebre:= temperatura>38.0;
END RELATION.
CONCEPT datos-cualitativos …
AXIOMS: hipertension:= presion-sangre;

Relaciones – Prolog
relacion(nombre, arg1, arg2)
relacion(abstraccion, datos-cuantitativos, datos-cualitativos)
axioma(concepto/relacion, expresion)
axioma(abstraccion, fiebre= (temperatura>38)).
axioma(datos-cualitativos, hipertension= presion-sangre)).

Inferencias
INFERENCE especificar
ROLES:
INPUT: evidencia-abstracta
OUTPUT:hipotesis
DOMAIN-VIEW: abstraccion
INFERENCE abstraer
ROLES:
INPUT: evidencia
OUTPUT: evidencia-abstracta
DOMAIN-VIEW: definicion

Inferencias – Prolog
inferencia (nombre, descripcion)
inferencia (abstraer, 'hacer una generalización de los datos').
inferencia (especificar, 'concretar una propiedad').
metaclase (inferencia, tipo I/O, nombre, descripcion)
metaclase(abstraer, entrada, evidencia, 'sintoma observado').
vista-dominio (inferencia, concepto/relacion)
vista-dominio(especificar, definicion).
papel (concepto/relacion, metaclase)
papel(evidencia, datos-cuantitativos).

Tareas
TASK diagnosticar;
ROLES:
INPUT: evidencia;
OUTPUT: hipotesis;
INTERMEDIATE: evidencia-abstracta;
CONTROL-STRUCTURE:
abstraer(evidencia->evidencia-abstracta);
especificar(evidencia-abstracta->hipotesis);
END TASK.

Tareas – Prolog
nombre_tarea(Var_Entrada, Var_Salida) :-
inferencias, condiciones.
Ejemplo:
diagnosticar (Evidencia, Hipotesis) :-
inferencia_call(abstraer, Evidencia, Evidencia-abstracta), inferencia_call (especificar, Evidencia-abstracta, Hipotesis).
inferencia_call (Nombre, Mentrada, Msalida) :-
inferencia(Nombre, _X), metaclase(Mentrada, entrada, Nombre), metaclase(Msalida, salida, Nombre), papel(Concepto,Mentrada), concepto(Concepto …

Tema 5- Diseño e Implementación
Indice del tema:
Arquitectura de un SBC y subsistemas típicos. Pasos de diseño
Formalismos de representación del conocimiento
Herramientas para la implementación de SBC

Sistemas de producción
Una regla no es más que la transcripción del conocimiento de una persona a un formato lógico.
Cadena de Inferencia: reglas que están interconectadas pues las conclusiones de unas son premisas para otras.
Intérprete : idenfica reglas aplicables y selecciona el orden en el que serán ejecutadas. Dos tipos:
Forward chaining o dirigido por los datos.
Backward chaining o dirigido por el resultado.

Lógica proposicional
La lógica proposicional se basa en determinar la verdad o falsedad de una proposición a partir de otras proposiciones.
Un hecho es una sentencia del modo:
proposición : los pájaros vuelan
La falsedad o verdad de una proposición vendrá dada por uno de los dos posibles valores: Cierto o Falso.
Sobre los hechos se pueden aplicar distintos operadores: Conjunción (AND), Disyunción (OR), Negación (NOT), Igualdad, (=), Implicación (=>).

Inferencia en la lógica proposicional
Modus Ponens:
p es T y p=>q es T podemos inferir : q es T
Modus Tollens
q es F y p=>q es T podemos inferir : p es F
Modus Ponendo Tollens
q es F y p OR q es T podemos inferir : p es T
Modus Tollendo Ponens
q es T y p AND q es T podemos inferir : p es T

Lógica de predicados de 1er orden
Permite razonar sobre las relaciones entre entidades, sirve para razonar sobre partes del universo del discurso.
La sintaxis está formada por constantes, variables, predicados, funciones, operadores lógicos y cuantificadores.
La inferencia permite, además de los mecanismos de la lógica proposicional, utilizar la especialización o instanciación.
Otras lógicas son:
Lógica modal que incluye estructuras del tipo “es necesario” “es posible”
Lógicas temporales con proposiciones del tipo “siempre” “a veces”

Programación lógica con restricciones
Un conjunto de atributos con un dominio de valores posibles finito.
Un conjunto de restricciones que condicionan los valores que pueden tomar los atributos anteriores.
Filtrado de hipótesis que asignan combinaciones de valores a los atributos anteriores.
Razonamiento temporal: puntual, intervalos, restricciones temporales.

Marcos o 'Frames'
Humanos agrupamos conocimiento en marcos conceptuales (Minsky, 1975). Tratar nuevas situaciones a partir del parecido con situaciones anteriores.
Marco o Frame con atributos valorados en un rango, con posible valor por defecto.
El valor de un atributo puede calcularse mediante procedimientos asociados (demonios) que se ejecutan cuando:
Se necesita. Se añade un determinado valor. Se cambia un determinado valor.
Jerarquía de marcos permite representar especialización y generalización.
Equiparación de marco pregunta con el que más encaje.

Redes semánticas
(Quillian,1968) para representar el conocimiento en frases.
Representan desde la semántica hasta relaciones causales.
Grafo dirigido etiquetado. Etiquetas de nodos son nombres (conceptos), de los arcos son verbos (relaciones).
Inferencia mediante herencia y equiparación de patrones.
Ventajas : Explícitas y sucintas. Reducen el tiempo de búsqueda.
Desventajas : No hay interpretaciones estándar. Se producen inferencias inválidas. Explosión combinatoria.

Incertidumbre
Sistemas de producción utilizan afirmaciones (hechos) sobro el mundo modelizado en la base de conocimientos.
¿Cómo tratar con conceptos que van más allá de las etiquetas “verdadero” y “falso”?
Los expertos aplican reglas de inferencia basadas en sus impresiones de las que no son capaces de afirmar la veracidad o falsedad.
¿De donde surge la incertidumbre?
Datos Incompletos
Datos ambiguos
Representación imprecisa de los datos

Razonamiento con incertidumbre
El objetivo es introducir esa incertidumbre en los SBC: cómo se representa, cómo se calcula y cómo se propaga por las reglas (desde las premisas a las conclusiones).
Métodos de representación de la incertidumbre:
Teorema de bayes: probabilidades
Factores de certidumbre
Teoría de Demster-Shafer
Conjuntos borrosos y lógica difusa

Repaso de Probabilidad
La probabilidad está entre 0 y 1. 1 es el espacio total.
La probabilidad de la unión de dos conjuntos disjuntos es la suma de las probabilidades.
La probabilidad condicional se define por: p(A ? X) = p(A/X) * p(X) = p(X/A) * p(A)
El teorema de Bayes consiste en: p(A/ X) = p(X/A) * p(A) / p(X)
La probabilidad total se define por: p(X) = p(X?x1) + p(X?x2) + .. = p(X/x1) * p(x1) + p(X/x2) * p(x2) + …
Luego Bayes queda: p(A/ X) = p(x1/A) * p(x1) / p(X/x1) * p(x1) + p(X/x2) * p(x2) + …

Reglas probabilísticas
IF Hipotesis H es Verdad THEN Evidencia E puede concluirse con probabilidad p.
Se puede escribir: H => E(p) donde p(E/H) = p
Y con el teorema de Bayes se puede aplicar un razonamiento abductivo t.q. P(H/E) = P(E/H) * p(H) / p(E)

Ejemplo de aplicación de Bayes
Dados: p(resfriado) = 0.2; p(estornudo/no resfriado) = 0.75; p(estornudo/resfriado) = 0.2.
Podemos calcular:
p(estornudo) = 0.75 * 0.2 + 0.2 * 0.8 = 0.31
p(resfriado/haya estornudado) = 0.75 * 0.2 / 0.31 = 0.48387
p(resfriado/no haya estornudado)=(1-0.75)*0.2/(1-0.31)=0.07246

Bayes con múltiples hipótesis y evidencias
Dadas m hipótesis y n evidencias independientes, tenemos:
P(Hi/E1 E2 ….En) = P(E1 E2 ….En/Hi) * p(Hi) / P(E1 E2 ….En) =

P(E1 /Hi) * P(E2 /Hi) * … * P(En/Hi) * p(Hi)
___________________________________
? P(E1 /Hk) * P(E2 /Hk) * … * P(En/Hk) * p(Hk)

Ejemplo de aplicación de Bayes con múltiples hipótesis y evidencias
Evidencias: estornudar (E1) y fiebre (E2)
Hipótesis: resfriado (H1), alergia (H2) y sensibilidad a la luz (H3).
Dados a priori:
p(H1) = 0.6, p(H2) = 0.3, p(H3) = 0.1
p(E1/H1) = 0.3, p(E1/H2) = 0.8, p(E1/H3) = 0.3
p(E2/H1) = 0.6, p(E2/H2) = 0.9, p(E2/H3) = 0.0
Podremos calcular P(H1/E1E2), P(H2/E1E2) y P(H3/E1E2)

Aplicación en Prospector
SBC pionero en aplicar probabilidad a un sistema de producción (Duda, Hart y Nilsson, 1978).
El conocimiento se representa como una red de inferencias.
Tipos de nodos: hechos (evidencias e), o deducibles (hipótesis h).
A partir de las probabilidades a priori de ambos tipos y de las relaciones causales entre los nodos, determina:
Grado de suficiencia de e para que se dé h
Grado de necesidad de e para que se dé h
Con estos datos Prospector era capaz de propagar la probabilidad en la ejecución de sus reglas.

Redes bayesianas
(Pearl, 1986) Representación mediante nodos (atributos y valores) y arcos (relaciones de causa-efecto)
Permiten: tanto razonar con la certeza de causa como con la certeza de efecto. Representadas con una matriz.
Motor de inferencias no modus ponens, en su lugar propagaremos certeza sobre causas y efectos en una red utilizando teorema de bayes.
Posibles estructuras de la red:
Cadena: una causa, un efecto.
Arbol: una causa, varios efectos
Red simplemente conexa: varias causas, varios efectos pero sin bucles.

Redes bayesianas
Creencia en hecho x dada una cadena de aconticimientos e.
La evidencia e se descompone e+ (causas) y e- (efectos)=> p(x / e+ , e- ) = p(e- / x, e+ ) * p(x / e+ ) / p(e- / e+ )
(Gp:) Consumo
de drogas

(Gp:) Estado de
ánimo

(Gp:) asesino

(Gp:) huellas

Nulo
Esporádico
Habitual
Apacible
Irritado
Furioso
Si
No
Seguro
Posible
Difícil
(Gp:) Apacible Irritado Furioso
Nulo 0.7 0.2 0.1
Esporádico 0.5 0.3 0.2
Habitual 0.3 0.4 0.3

(Gp:) Si No
Apacible 0.4 0.6
Irritado 0.6 0.4
Furioso 0.8 0.2

(Gp:) Seguro Posible Difícil
Si 0.7 0.2 0.1
No 0.1 0.2 0.7

Limitaciones del razonamiento probabilístico
Necesidad de demasiados datos para conseguir una base de conocimiento probabilístico.
¿En qué se basan las probabilidades a priori?.
Reducción de la relación entre conceptos a un conjunto de números.
Está reducción hace imposible de seguir el razonamiento.

Factores de certidumbre
(Mycin, 1979).
FC: grado de creencia en las hipótesis dadas las evidencias:
IF EVIDENCIA THEN HIPÓTESIS (FC)
Creencia positiva (0,1) grado en el que la creencia en la hipótesis es soportada por la evidencia: CP= ( p(h/e) -p(h) ) / (1 – p(h) ) .
Creencia negativa (0,1) grado en el que la no-creencia en la hipótesis es soportada por la evidencia CN= (p(h) – p(h/e) ) / p(h).
Factor de Certidumbre (-1, 1 )
FC= (CP-CN) / (1- min(CP,CN))

Factores de certidumbre
Las evidencias son verdaderas o falsas en un cierto grado.
Las evidencias disparan ‘n’ reglas con un cierto grado.
El FC de una hipótesis es la acumulación de la evidencia de varias reglas.
Grado de hipótesis viene de los grados de las evidencias, de los FC y de la acumulación de la evidencia de varias reglas.
Cómo se propagan:
FC de premisa = min(FC de las premisas ) para el AND
FC de premisa = max(FC de las premisas ) para el OR
FC de conclusión = FC de la premisa * FC de la regla

Factores de certidumbre
Como se acumulan los FC:
FC revisado ( FCr ) es función de FC antiguo ( FCa ) y el FC nuevo ( FCn ):
Si FCa y FCn son > 0 entonces FCr = FCa + FCn * (1-FCa)
Si los dos son negativos entonces FCn = -FCr( -FCn, -FCa )
Si uno es negativo FCn = (FCa + FCn ) / (1 – min(|FCa|, |FCn| ) )

Ejemplo de factores de certidumbre
Robo del coche de Tim.
R1: IF el acusado tiene un motivo AND el acusado tiene oportunidad
THEN el acusado es culpable del crimen (FC = 0.6)
R2: IF el acusado tiene coartada
THEN el acusado es culpable (FC = -0.8)
R3: IF las huellas dactilares del acusado están en el coche
THEN el acusado es culpable (FC = 0.4)
R4: IF las llaves están en el coche
THEN el acusado tiene oportunidad (FC = 0.9)
R5: IF al acusado no le gusta Tim
THEN el acusado tiene un motivo (FC = 0.5)
R6: IF el acusado necesita transporte
THEN el acusado tiene motivo (FC = 0.9)
R7: IF las huellas dactilares del acusado están en las llaves del coche
THEN el acusado es culpable (FC = 0.7)

Ejemplo de factores de certidumbre
E1: Mike necesita transporte (FC = 1.0) E2: John no necesita transporte (FC = 1.0)
E3: Las huellas digitales de Mike están en el coche (FC = 1.0)
E4: Las huellas digitales de John no están en el coche (FC = 1.0)
E5: Las huellas digitales de Mike no están en las llaves del coche (FC = 1.0)
E6: Las huellas digitales de John están en las llaves del coche (FC = 1.0)
E7: Las llaves de Tim estaban en el coche (FC = 1.0)
E8: A Mike no le gusta Tim (FC = 0.6) E9: A John le gusta Tim (FC = 0.8)
E10: Mike tiene una coartada (FC = 0.85) E11: John no tiene una coartada (FC = 0.2)

Ejemplo de factores de certidumbre
(Gp:) El acusado necesita transporte

(Gp:) Al acusado no le gusta Tim

(Gp:) Las llaves están en el coche

(Gp:) R6

(Gp:) R5

(Gp:) R4

(Gp:) El acusado tiene motivo

(Gp:) 0.5

(Gp:) 0.9

(Gp:) El acusado tiene oportunidad

(Gp:) 0.9

(Gp:) R1

(Gp:) El acusado tiene coartada

(Gp:) R2

(Gp:) El acusado es culpable

(Gp:) R3

(Gp:) Las huellas del acusado están en las llaves del coche

(Gp:) R7

(Gp:) Las huellas del acusado están en el coche

(Gp:) -0.80

(Gp:) 0.6

(Gp:) 0.4

(Gp:) 0.7

Ejemplo de factores de certidumbre
Hipótesis H1: Mike robó el coche de Tim (FC=0).
Subhipótesis H11: Mike tiene un motivo (FC=0).
Con la regla R6 (FC=0.9) sobre E1 (Necesidad de transporte, FC=1):
FCn(H11) = 0.9 * 1.0 = 0.9
FCr(H11) = 0 + 0.9 * (1 – 0) = 0.9
Con la regla R5 (FC= 0.5) sobre E8 (No le gusta Tim, FC=0.6)
FCn(H11) = 0.5 * 0.6 = 0.3
FCr(H11) = 0.9 + 0.3 * (1 – 0.9) = 0.93

Ejemplo de factores de certidumbre
Subhipótesis H12: Mike tiene la oportunidad (FC=0)
Con la regla R4 (FC= 0.9) sobre E7 (Llaves en el coche, FC=1):
FCn(H12) = 0.9 * 1.0 = 0.9
FCr(H12) = 0 + 0.9 * ( 1 – 0) = 0.9
Con la regla R1 (FC=0.6) sobre las subhipótesis H11 (FC=0.93 ) y H12 (FC=0.9), tenemos:
FC(H1)= min (0.9, 0.93)*0.6= 0.54
FCr(H1)= 0 + 0.54 * (1-0) = 0.54

Ejemplo de factores de certidumbre
Con la regla R2 (FC= -0.8) sobre la evidencia E10 (FC=0.85), tenemos:
FCn(H1) = 0.85 * (-0.8) = -0.68
FCr(H1) = (0.54 – 0.68) / (1- 0.54) = -0.3
Con la regla R3 (FC= 0.4) sobre la evidencia E3 (FC= 1) tenemos:
FCn(H1) = 1 * 0.4 = 0.4
FCr(H1) = (0.4 –0.3) / (1- 0.3) = 0.14
Con la regla R7 (FC= 0.7) sobre la evidencia E5 (FC=1) tenemos:
FCn(H1)= 1 * 0.7 = 0.7
FCr(H1) = 0.14 + 0.7 * (1 – 0.14) = 0.74
Se deja planteado como ejercicio calcular el FC de la hipótesis H2 de que John robó el coche de Tim.

Teoría de Dempster-Shafer
Se parte de un conjunto de posibles conclusiones : ? = {?1, ?2, …., ?n} Mutuamente exclusivo y exhaustivo.
Masa m, valor entre 0 y 1, probabilidad de que ocurra una de todas las posibles combinaciones de posibles soluciones.
Creencia en A ={?1, ?2}: Bel(A) = m(?1) + m(?2) + m(?1, ?2 )
Plausabilidad de A ={?1, ?2}: P*(A) = 1- Bel(Ac)
Certidumbre definida por el intervalo : [Bel(A), P*(A)]

Limitaciones de Dempster-Shafer
Representa certidumbre sobre la certidumbre
La creencia en A y Ac no agota todas las posibilidades, puede existir un grado de ignorancia.
Es un procedimiento complejo
Necesita de la enumeración de todos los casos posibles
No se define el origen de la masa de probabilidad.

Lógica borrosa o difusa: Zadeh
Justificación:
Vaguedad: dificultad para establecer los límites precisos de la definición de un término. Por ejemplo ‘joven’
Ambigüedad: en las relaciones que se establecen de un término a varios, elección entre varias alternativas.
Propuesta de Zadeh (1964) para operar con términos vagos:
El concepto borroso o difuso (p.e. ‘alto’) se representa mediante una función de pertenencia ? de un objeto (p.e. ‘juan’) a dicho concepto. Esta función establece el grado de compatibilidad de la afirmación de que ‘juan es alto’ con valores distintos de 0 y 1.

Lógica borrosa o difusa: Sugeno
Propuesta de Sugeno (1977) para aplicar el concepto ‘difuso’ en el contexto de la ambigüedad:
Dado un objeto x del universo X, dividido en conjuntos no borrosos A,
cada uno de estos conjuntos tiene asignado una función gx(A) entre 0 y 1, que representa el grado de ‘borrosidad’ de la afirmación ‘x pertenece a A’.
Este grado puede ser interpretado como una probabilidad, creencia o posibilidad.

Lógica borrosa o difusa: Unificación
Unificación de Zadeh (1978): Distribución de posibilidad inducica por un conjunto borroso.
La distribución de posibilidad ? sobre el universo X, asocia a cada elemento x la posibilidad de que sea un valor de la variable v definida sobre x: ?(v=x) = ? (x) = ?A(x)
Así la expresión de la distribución de posibilidad es equivalente a un conjunto borroso, por lo que se pueden aplicar los conceptos de la lógica borrosa sobre las distribuciones de posibilidad.

Un conjunto borroso o difuso

Compatibilidad de un valor con un conjunto borroso

Compatibilidad de un conjunto borroso con otro

Operaciones con conjuntos borrosos
Sean los conceptos borrosos A y B definidos por ?A y ?B:

“NOT A” se representa mediante : 1 – ? A(x)
Luckasiewicz ?A=>B(x,y)= min{1, 1 – ? A(x) + ? B(y)}
Mamdani ?A=>B(x,y)= min{? A(x), ? B(y) }

Inferencia borrosa o difusa
Inferencia clásica Modus Ponens: A AND (A => B).
Así cuando ‘x es A’ es verdad y ‘A=>B’ también, entonces B es verdad.
Y al contrario, cuando ‘x es A*’ es verdad, entonces B resulta ser falso.
Utilizando las fórmulas de MAX-MIN y Mamdani, obtendremos finalmente:
?B*(y) = Sup{ Min{ Min{?A*(x), ?A(x)}, ?B(y) } }

Inferencia borrosa gráficamente

Sistema borroso

Defuzzificación
Centro de gravedad
Singletons
Centroides
(Gp:) VL

(Gp:) L

(Gp:) M

(Gp:) H

(Gp:) VH

(Gp:) ?

Ejemplo de lógica borrosa
SI (distancia_1 es LEJOS OR distancia_2 es MUY LEJOS) ENTONCES Velocidad_1 es NORMAL
Los antecedentes tienen un grado de pertenencia de 0.6 y 0.4
La conclusión tiene un grado de activación, ?:
distancia_1 es LEJOS OR distancia_2 es MUY LEJOS
max{0.6,0.4}= 0.6
Por tanto el grado de activación de (Velocidad_1 es NORMAL) es: ? = 0.6
SI (distancia_2 es MUY LEJOS) ENTONCES Velocidad_1 es ALTO
La conclusión tiene un grado de activación, ? = 0.6

Ejemplo de lógica borrosa

Ejemplo de lógica borrosa
NORMAL:
Centro: 40 Pertenencia: 0.6
Área: [ 0.6 * (40+28) ] / 2 = 20.4
ALTO:
Centro: 70 Pertenencia: 0.4
Área: [ 0.4 * (40+32) ] / 2 = 14.4
Centroide:
20.4 * (40) + 14.4 * (70)
—————————— = 52.41
20.4 +14.4

Limitaciones de la lógica borrosa
Se permite la representación de conceptos definidos con límites precisos así como definidos con límites imprecisos
Se permiten calificadores del modo mucho, poco, varios,… que se representan mediante modificaciones de la función de pertenencia del conjunto básico. Por ejemplo de cerca (? (x)) el concepto muy cercano es el cuadrado (?(x)2) del conjunto cerca.
En los sistemas lógicos bi-valuados una proposición está asociada con un valor de verdad, en lógica borrosa está asociada con: una verdad borrosa, resultado de aplicar la tabla de verdad de la implicación lógica que se escoja.

Sistemas de mantenimiento de la verdad
Razonamiento no monótono: existencia de excepciones, redefinición de proposiciones, procedimientos para restar evidencia a premisas, etc.
Los sistemas de mantenimiento de la verdad procuran evitar trabajos inútiles de comprobación de que se verifican unas condiciones. Se ocupan de mantener de forma consistente las creencias relevantes en función de las modificaciones e identifica contradicciones.

Mecanismos de Control
Los mecanismos de control ayudan a manejar los conocimientos del dominio: aplicar estrategias, resolver excepciones.
Muchas veces no es suficiente con la base de conocimiento y el motor de inferencias.
Estos mecanismos pueden ser:
De bajo nivel: La creación y resolución del conjunto conflicto.
De alto nivel: decisiones estratégicas (cambio de objetivo o de subproblema).

Control de bajo nivel
Para la resolución del conjunto conflicto:
Especificidad, novedad, refracción, prioridades.
Para la creación del conjunto conflicto:
Algoritmos de búsqueda: en amplitud, en profundidad, escalada, etc.

Búsqueda en profundidad
Generate – and – Test: prueba y error
Hill Climbing (Escalada)
1. Se genera la primera solución propuesta como antes. Si lo es acaba sino continuamos.
2. Aplicamos al nodo un conjunto de reglas posibles y tenemos un conjunto de soluciones propuestas.
3. Para cada elemento de ese conjunto:
a) Aplicamos la función de escalada, si es solución fin,
b) si no, ver si es mejor que los anteriores
4. Tomar el mejor y utilizarlo como solución propuesta.
5. Volver a 1

Búsqueda en amplitud
Consiste en examinar todos los nodos de un mismo nivel del árbol de búsqueda de solución, antes que cualquiera de los nodos del siguiente nivel. Este método garantiza encontrar la solución si esta existe, pero: Requiere gran cantidad de memoria, gran cantidad de trabajo y además operadores irrelevantes pueden aumentar el número de nodos a explorar.
Búsqueda en amplitud + profundidad : Best – First
En cada paso se selecciona el nodo más prometedor de todos los generados, aplicando una función heurística. Este nodo se expande, y todos lo nuevos nodos se agrupan con los anteriormente generados, escogiendo entre todos el más prometedor.

Control de alto nivel
Cuando el problema es complejo puede no ser suficiente.
La complejidad se debe a:
La cantidad de conocimiento implicado.
La necesidad de combinar el uso de conocimiento representado mediante distintos formalismos.
Dificultad de representar y manejar el estado de un problema.
Tratan de:
Cambiar de estado parcialmente
Centrarse en una parte del estado
Divide y vencerás

Control de alto nivel: metarreglas
Con los formalismos de representación habituales, por ejemplo: reglas de producción.
En este caso podemos distinguir el control implícito del explícito. Cuando las reglas y el conocimiento de control está claramente diferenciado en un módulo de control ? metarreglas.
Normalmente se ocupan de:
Parar/activar ejecución
Añadir/reordenar/eliminar reglas o metas
Modificar criterios resolución conjunto conflicto

Arquitecturas de control de alto nivel
Se utilizan arquitecturas específicas para resolver los problemas de control en SBC complejos.
Sirven para coordinar el conocimiento de diversas fuentes para resolver el problema.
Veremos tres arquitecturas: agendas, pizarras y sistemas de agentes.

Agendas
La idea general es la utilización por parte del sistema de una estructura global en la que se anotan las acciones a realizar y en la que se registran todos los cambios que se van produciendo.
Por lo tanto una agenda es una lista de tareas que puede realizar el sistema. Asociado a cada acción tenemos: una lista de razones y una medida de la utilidad de la acción.
Un problema muy importante es el dimensionamiento de la tarea ni muy grandes, ni muy pequeñas.
La comunicación entre los distintos módulos se realiza a través de la agenda, los módulos comparten información sobre las tareas a realizar, pero no saben nada de los otros módulos.

Pizarra
Es una abstracción de un grupo de expertos colaborando para resolver un problema.
Cada uno de los cuales posee conocimiento que puede ser relevante en algún momento del proceso de solución.
Todos ven en la pizarra la última solución parcial. Cualquiera puede escribir una contribución parcial a la solución. La solución final va surgiendo al combinarse todas las contribuciones de los expertos.
Se necesita un método para evaluar la contribución de cada experto y determinar a quién se le permite escribir.
La información debe escribirse de modo que todos los expertos la comprendan.

Componentes de la pizarra
La pizarra puede dividirse en diferentes niveles de abstracción organizados de forma jerárquica.
Las fuentes de conocimiento:
examinan la pizarra para generar conclusiones y modificar el foco de atención del problema.
Cada una se dispara cuando puede contribuir a la solución, al cumplir condiciones separadas en dos campos:
Están aisladas unas de otras, excepto por la pizarra.
En general el proceso de control funciona porque las fuentes:
modifican el contenido de la pizarra.
indican la contribución que puede hacer a la solución.

Ejemplos de pizarra
Alumnoo
Alumnoo
Alumnoo
Alumnoo
Profesoro
Pizarrao

Ejemplo de pizarra
Corredoro
Corredoro
Corredoro
Corredoro
Operadoro
Pizarrao

Pizarras
Ventajas:
Los expertos actúan en orden determinado por el progreso de la solución.
Es fácil añadir nuevos expertos.
Diferentes aspectos del problema se pueden considerar simultáneamente por diferentes grupos de expertos usando diferentes áreas de la pizarra (p.e. puzzle).
Como todas las interacciones entre los expertos se producen a través de la pizarra el control del proceso de solución se puede ejercer determinando el orden de acceso de los expertos.

Arquitecturas multiagentes
Mediante fuentes de conocimiento dotadas de autonomía (agentes).

Redes: Resolución distribuida de problemas
Proceso autónomo: Agente Software
Con objetivo común: MAS
A semejanza humana: Agente Inteligente
¿qué agentes?

Objetivos y necesidades
Persiguen mejorar la eficacia global de las fuentes de conocimiento.
Necesitan un sistema de mantenimiento de la verdad distribuido para garantizar la consistencia:
Elemento central: coordinador, ontología.
Asignación de roles
Descripción de secuencia y dependencia de la división del problema en partes
Sincronización

Tipos de Sistemas de agentes
Coordinación centralizada (comunicación intermediada):
Fuertemente: agente planificador
Débilmente: agente negociador
Coordinación distribuida (comunicación directa):
con objetivos en común: cooperación
Sin objetivos en común: competición

Un agente por dentro
Dos tipos de arquitecturas internas de un agente:
Por sus frutos los conoceréis: reactivas
– Las obras sin fe están muertas: deliberativas

Herramientas para construir agentes
JAM: docencia de agentes
Aglets de IBM
JATlite Univ. de Stanford.
JAFMAS, Univ. de Cincinnati
JADE: Comunicación
JADEX: Deliberativos.

Historia
Hoy día utilizamos motores de inferencia ya programados.
Antes se programaban tb al construir el SBC
Pionero fue EMYCIN: con encadenamiento hacia atrás, factores de certeza y facilidades de explicación.
Otro fue R1/Xcon del que surgió OPS5.

Lenguajes
Lenguajes:
Common-Lisp: ANSI, UFA-Soft, Allegro, etc.,
Prolog: www.swi-prolog.org,
CLIPS y FuzzyCLIPS: www.ghg.net/clips ai.iit.nrc.ca/IR_public/ fuzzy/fuzzyClips
JESS: herzberg.ca.sandia.gov/jess

Entornos
Entornos integrados con facilidades e interfaz.
Algunas muy orientadas a la adquisición: OPAL, SALT
Características:
Versatilidad de representación.
Depuración
Eficiencia
Ayuda para incorporar capacidad explicativa
Integración con otros lenguajes/aplicaciones.

FOCL
FOCL escrito en Common Lisp. Incluye facilidad para apredizaje automático desde ejemplos, un interfaz gráfico para modificar/escribir reglas y hechos, y un intérprete con encadenamiento hacia atrás.
Disponible mediante ftp anónimo en:
ics.uci.edu:/pub/machine-learning-programs/

RT-Experts
Rápida ejecución. Real Time Expert
Facilidad para integrarse con programas escritos en C.
Encadenamiento hacia atrás.
Incluye librería en C para ejecutar motor de inferencias.
world.std.com:/vendors/rtis/rtexpert

MIKE
Micro interpreter for knowledge engineering
Implementada en prolog por la Open Univ. (Reino Unido).
Conflictos definidos por usuario.
Encadenamiento hacia atrás y hacia adelante.
Facilidad para representar marcos y para integrar autoexplicación.
Herramientas gráficas para seguimiento de la ejecución
Disponible mediante ftp anónimo en: hcrl.open.ac.uk

MOBAL
Representaciones del dominio en lógica de primer orden.
Facilidad para la adquisición de conocimiento y para su verificación mediante interfaz gráfico.
Incluye herramientas de aprendizaje automático.
Mediante ftp anónimo en: ftp.gmd.de:/gmd/mlt/Mobal/

Babylon
Incluye facilidades para marcos, programación con restricciones.
Está escrito en Common Lisp
Disponible en: http://www.gmd.de/

Entornos comerciales
Acquire: énfasis en adquisición http://vvv.com/ai/
Art: Integración con C, ADA y Lisp. Acceso a BBDD http://www.brightware.com/
GBB: pizarras. ftp.cs.umass.edu:/gbb/
GURU: fuzzy y BBDD http://www.savitar.com/prod_guru.htm
KEE: reglas y marcos. Búsqueda. Integrable en lisp.
Smart elements o Nexpert object: notación gráfica muy rica. Marcos.

Entornos comerciales
Goldworks: integración con c. Marcos, reglas. http://www.goldhill-inc.com/goldworks.htm
G2: tiempo real, OO y reglas (atrás y adelante). Integración con C y Fortran
M.4: http://www.teknowledge.com/M4/proddesc.html
Blaze Advisor: http://www.fairisaac.com/Fairisaac/Solutions
ILOG Jrules: http://www.ilog.com/products/jrules